package com.chenken;

/**
 *	归并排序 -分治
 *	1.不断地将当前序列平均分割成2个子序列，分割到不能再分割为止
 * 	2.不断地将2个子序列合并成一个有序序列，直到最终只剩下一个有序序列
 */
public class MergeSort<T extends Comparable<T>> extends Sort<T> {

	@Override
	protected void sort() {
		if(arrays == null || arrays.length == 0) {
			return;
		}
		mergeSort(0,arrays.length);
	}
	
	/**
	 * 复杂度分析
	 * 	 T(n) = T(n/2) + T(n/2) + O(n)
	 * 	 T(n) = 2 * T(n/2) + O(n)
	 *   T(1) = O(1)
	 *   T(n)/n = T(n/2)/(n/2) + O(1)
	 *   
	 *   令S(n) = T(n)/n
	 *   S(1) = T(1) = O(1)
	 *   S(n) = S(n/2) + O(1) = S(n/4) + O(2) = S(n/8) + O(3) = S(n/2^k) + O(k) = S(1) + O(logn) = O(logn)
	 *   
	 *   结论:T(n) = n * S(n) =  O(nlogn)
	 *   由于归并排序总是平均分割子序列，所以最好，最坏，平均时间复杂度都是O(nlogn),属于稳定的排序
	 *   空间复杂度为O(n/2 + logn) = O(n)
	 */
	private void mergeSort(int begin, int end) {
		if(end - begin < 2) return;
		int mid = (begin + end) >> 1;
		mergeSort(begin, mid);//分割
		mergeSort(mid, end);//分割
		merge(begin,mid,end);//合并
	}

	/**
	 * 将[begin,mid)和[mid,end)范围的序列合并成一个有序序列
	 * note:需要merge的2个序列存在于同一个数组中，并且是挨在一起的
	 * 为了更好的完成merge操作，需要将左边的数组[begin,mid)备份出来
	 * @param begin
	 * @param mid
	 * @param end
	 */
	@SuppressWarnings("unchecked")
	private void merge(int begin, int mid, int end) {
		int li = 0,le = mid-begin;//左边数组的开始和结束位
		int ri = mid,re = end;//右边数组的开始和结束位
		int ai = begin;
		
		//备份左边数组
		T[] leftArray = (T[]) new Comparable[le];
		for(int i = li;i<le;i++) {
			leftArray[i] = arrays[begin + i];
		}
		//如果左边没有结束
		while(li < le) {
			//如果右边数组的元素比左边数组的元素小
			if(ri < re && compare(arrays[ri], leftArray[li]) < 0) {
				//将右边数组的元素替换到左边数组位
				arrays[ai++] = arrays[ri++];
			}else {
				//将左边数组的元素放在右边数组位
				arrays[ai++] = leftArray[li++];
			}
		}
	}

}
